package com.code.leetcode._202508;

//67 二进制求和
public class AddBinary {
    /**
     * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     * 示例1：输入:a = "11", b = "1"
     * 输出："100"
     * 示例2：输入：a = "1010", b = "1011"
     * 输出："10101"
     **/
    public static void main(String[] args) {
        AddBinary a = new AddBinary();
        System.out.println(a.addBinary("11", "1"));
    }

    /**
     * 考虑一个最朴素的方法：先将a和b转化成十进制数，求和后再转化成二进制数。利用JAVA自带的高精度运算，
     * 我们可以很简单地写出这个程序：
     **/
    public String addBinary1(String a, String b) {
        return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }

    /**
     * 如果a地位数是n，b地位数为m，这个算法地渐进时间复杂度为O(n+m)。但是这里非常简单地实现基于JAVA本身
     * 的高精度功能，在其他的语言中可能并不适用，并且再Java中：
     * 1、如果字符串超过33位，不能转化为Integer。
     * 2、如果字符串超过65位，不能转化位Long
     * 3、如果字符串超过500000001位，不能转化位BigInteger
     * 因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。
     * 模拟
     * 我们可以借鉴列竖式的方法，末尾对齐，逐位相加。在十进制的计算中逢十进一，二进制中我们需要逢二进一
     * 具体的，我们可以取n=max{|a|,|b|}，循环n次，从最低位开始遍历。我们使用一个变量carry表示上一个
     * 位置的进位，初始值位0。记当前位置对其的两个位位ai和bi，则每一位的答案位(carry+ai+bi)mod2，下一位
     * 的进位位(carry+ai+bi)/2。重复上述步骤，知道数字a和b的每一位计算完毕。最后如果carry的最高位不为0
     * 则将最高位添加到计算结果的末尾。
     * 注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位，
     * 当然你也可以直接把a和b中短的那一个补0直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序
     * 存入答案字符串内，最终将答案串反转。
     **/
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; i++) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }

}
